package oj.oj_606;

import oj.oj_144.TreeNode;

/**
 * 根据二叉树创建字符串
 * https://leetcode.cn/problems/construct-string-from-binary-tree/
 */
public class Solution {
    public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        // 得到了前序遍历的结果
        // 删除第一个字符 '(' 和 最后一个字符 ')'
        sb.deleteCharAt(0);   // 删除 下标 [0] 的字符，也就是 '('
        sb.deleteCharAt(sb.length() - 1); // 删除最后一个字符，也就是 ')'
        return sb.toString();
    }

    // 字符串不可变的，我们这里想对字符串不断地添加东西（频繁修改）
    // 不应该用 String 对象，而应该用 StringBuilder(关于 char 的可变的顺序表)； String 是 关于 char 的不可变顺序表
    // 备注：能不直接用数组就不要直接用数组，因为控制好下标是非常难的事情
    // 同时也不符合封装的思想（数组 和 下标本来就应该是一体 -> 区间概念)
    private void preorder(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("()");    // 代表是空树
            return;
        }

        sb.append('(');
        if (root.left == null && root.right == null) {
            // 只有一个根结点的情况
            sb.append(root.val);    // 不走左右子树的了
        } else if (root.left == null && root.right != null) {
            // 左空右不为空
            sb.append(root.val);
            preorder(root.left, sb);
            preorder(root.right, sb);
        } else if (root.left != null && root.right == null) {
            // 左不为空右为空
            sb.append(root.val);
            preorder(root.left, sb);
            // 不走右子树了
        } else {
            // 左右都不为空
            sb.append(root.val);
            preorder(root.left, sb);
            preorder(root.right, sb);
        }
        sb.append(')');
    }
}

